package 回溯;

import java.util.ArrayList;
import java.util.List;

//https://leetcode.cn/problems/combination-sum/
public class 组合总和 {
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> ail = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        fun_DFS(candidates , target , 0);
        return list;
    }
    public void fun_DFS(int[] candidates , int target , int index){
        //当索引与长度相等，很明显这条路走完也没有合适的
        if (index == candidates.length){
            return;
        }
        if (target == 0){
            //如果值减到0了，说明这条路是正确的把他加进去
            list.add(new ArrayList<>(ail));
            return;
        }
        //不用当前索引值查看能否完成跟《二进制手表》有点像，类似与循环时确定一个值，只考虑后面的
        fun_DFS(candidates , target , index + 1);
        if (target - candidates[index] >= 0){
            ail.add(candidates[index]);
            fun_DFS(candidates , target - candidates[index] , index);
            ail.remove(ail.size() - 1);
        }
    }

}
